#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

 

示例 1：


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//递归方式实现
//返回头结点 递归方式是写对了我草
//也可以重新写个函数
TreeNode* sortedArrayToBST(vector<int>& nums) {
    if (nums.size()==0)
        return nullptr;

    TreeNode* root=  new TreeNode(nums[nums.size()/2]);


    vector<int> leftN(nums.begin(),nums.begin()+(nums.size()/2));
    vector<int> rightN(nums.begin()+(nums.size()/2)+1,nums.end());
    root->left= sortedArrayToBST(leftN);



    root->right=sortedArrayToBST(rightN);

    return root;

}


// 这种方式我不会

//TreeNode* sortedArrayToBST1(vector<int>& nums) {
//    if (nums.size()==0)
//        return nullptr;
//
//    TreeNode* root=  new TreeNode(nums[nums.size()/2]);
//
//    //左子树构建
//    for (int i = 0; i <=nums[nums.size()/2] ; ++i) {
//
//
//    }
//
//
//    return root;
//
//}